题解：P10414 [蓝桥杯 2023 国 A] 2023 次方

思路

为了求解 $2^{(3^{(4^{(\ldots ^{2023})})})}$（即指数塔从 $2$ 开始，指数为 $3$，再指数为 $4$，依此类推至 $2023$），需要利用模运算的性质和数论工具，因为直接计算巨大的指数塔不可行。$2023$ 可分解为 $2023 = 7 \times 17^2 = 7 \times 289$，且 $7$ 和 $289$ 互质（因为 $\gcd(7, 289) = 1$，$289 = 17^2$ 不含因子 $7$）。因此，使用中国剩余定理（CRT），分别计算模 $7$ 和模 $289$ 的结果，再组合得到模 $2023$ 的解。

Step 1：计算 $2^ {(3^{(4^{(\ldots ^{2023})})})} \mod 7$。

模数 $7$ 是质数，且 $\gcd(2, 7) = 1$，因此可应用欧拉定理：$\phi(7) = 6$，有 $2^6 \equiv 1 \mod 7$。
设指数 $k = 3^{4^{\cdots^{2023}}}$，则需求解 $2^k \mod 7$。根据欧拉定理，$2^k \equiv 2^{k \mod 6} \mod 7$（因为 $k \geq 1$）。
现在计算 $k \mod 6$，即 $3^{4^{\cdots^{2023}}} \mod 6$。
- 注意到 $3 \equiv 3 \mod 6$，且对于任意正整数指数 $m \geq 1$，有 $3^m \equiv 3 \mod 6$（因为 $3^1 = 3$，$3^2 = 9 \equiv 3$，$3^3 = 27 \equiv 3$，归纳得 $3^m - 3 = 3(3^{m-1} - 1)$，而 $3^{m-1}$ 是奇数，减 $1$ 为偶数，故可被 $2$ 整除；同时 $3$ 的存在使整体被 $6$ 整除）。
- 因此，$k = 3^{4^{\cdots^{2023}}} \equiv 3 \mod 6$（因为指数 $4^{\cdots^{2023}} \geq 1$)。
代入：$2^k \equiv 2^3 = 8 \equiv 1 \mod 7$（因为 $8 - 7 = 1$)。
所以，$2^{3^{4^{\cdots^{2023}}}} \equiv 1 \mod 7$。

Step 2：计算 $2^ {3^{4^{\cdots^{2023}}}} \mod 289$。

模数 $289 = 17^2$，且 $\gcd(2, 289) = 1$（因为 $289$ 是奇数），因此可应用欧拉定理：$\phi(289) = 289 \times (1 - \frac{1}{17}) = 289 \times \frac{16}{17} = 17 \times 16 = 272$，有 $2^{272} \equiv 1 \mod 289$。
设指数 $k = 3^{4^{\cdots^{2023}}}$，则需求解 $2^k \mod 289$。根据欧拉定理，$2^k \equiv 2^{k \mod 272} \mod 289$（因为 $k \geq 1$)。
现在计算 $k \mod 272$，即 $3^{4^{\cdots^{2023}}} \mod 272$。
- 分解 $272 = 16 \times 17$（因为 $272 = 2^4 \times 17$)，且 $\gcd(16, 17) = 1$，因此使用 CRT，分别计算模 $16$ 和模 $17$ 的结果。
- 计算 $k \mod 16$：
  - $k = 3^{m}$ 其中 $m = 4^{5^{\cdots^{2023}}}$。
  - $\gcd(3, 16) = 1$，且 $\phi(16) = 8$（因为 $16 = 2^4$，$\phi(2^4) = 2^{4-1} = 8$)，有 $3^8 \equiv 1 \mod 16$。实际上，计算得 $3^4 = 81 \equiv 1 \mod 16$（因为 $16 \times 5 = 80$，$81 - 80 = 1$)，阶为 $4$，因此 $3^m \equiv 3^{m \mod 4} \mod 16$。
  - 计算 $m \mod 4$，即 $4^{n} \mod 4$ 其中 $n = 5^{6^{\cdots^{2023}}}$。
    - 对于 $n \geq 1$，有 $4^n \equiv 0 \mod 4$（因为 $4^1 = 4 \equiv 0$，$4^2 = 16 \equiv 0$，归纳成立）。
    - 因此 $m = 4^n \equiv 0 \mod 4$（因为 $n \geq 5 \geq 1$)。
  - 代入：$m \equiv 0 \mod 4$，所以 $3^m \equiv 3^{4l} = (3^4)^l \equiv 1^l = 1 \mod 16$（因为 $m = 4l$ 且 $m \geq 4$)。
  - 故 $k \equiv 1 \mod 16$。
- 计算 $k \mod 17$：
  - $k = 3^{m}$ 其中 $m = 4^{5^{\cdots^{2023}}}$。
  - 模数 $17$ 是质数，$\gcd(3, 17) = 1$，$\phi(17) = 16$，有 $3^{16} \equiv 1 \mod 17$，因此 $3^m \equiv 3^{m \mod 16} \mod 17$。
  - 计算 $m \mod 16$，即 $4^{n} \mod 16$ 其中 $n = 5^{6^{\cdots^{2023}}}$。
    - 对于 $n \geq 2$，有 $4^n \equiv 0 \mod 16$（因为 $4^2 = 16 \equiv 0$，$4^3 = 64 \equiv 0$，归纳成立）。
    - 因此 $m = 4^n \equiv 0 \mod 16$（因为 $n \geq 5 \geq 2$)。
  - 代入：$m \equiv 0 \mod 16$，所以 $3^m \equiv 3^{16l} = (3^{16})^l \equiv 1^l = 1 \mod 17$（因为 $m = 16l$ 且 $m \geq 16$)。
  - 故 $k \equiv 1 \mod 17$。
- 现在有 $k \equiv 1 \mod 16$ 和 $k \equiv 1 \mod 17$。由于 $16$ 和 $17$ 互质，根据 CRT，$k \equiv 1 \mod (16 \times 17) = \mod 272$（因为解唯一且 $k - 1$ 可被 $16$ 和 $17$ 整除）。
因此 $k \equiv 1 \mod 272$。
代入模 $289$ 的表达式：$2^k \equiv 2^{272l + 1} = (2^{272})^l \cdot 2 \equiv 1^l \cdot 2 = 2 \mod 289$（因为 $2^{272} \equiv 1 \mod 289$）。
所以，$2^{3^{4^{\cdots^{2023}}}} \equiv 2 \mod 289$。

Step 3：使用中国剩余定理组合结果。

现在有：
- $x \equiv 1 \mod 7$
- $x \equiv 2 \mod 289$
设 $x = 289a + 2$。
代入第一式：$289a + 2 \equiv 1 \mod 7$。
计算 $289 \mod 7$: $289 \div 7 = 41 \times 7 = 287$，余数 $289 - 287 = 2$，所以 $289 \equiv 2 \mod 7$。
因此 $2a + 2 \equiv 1 \mod 7$。
化简：$2a \equiv -1 \equiv 6 \mod 7$。
解 $a$: 两边乘 $2$ 在模 $7$ 下的逆元（因为 $\gcd(2, 7) = 1$，逆元为 $4$，因 $2 \times 4 = 8 \equiv 1 \mod 7$)，得 $a \equiv 6 \times 4 = 24 \equiv 3 \mod 7$（因为 $24 - 3 \times 7 = 24 - 21 = 3$)。
所以 $a = 7b + 3$。
代入：$x = 289(7b + 3) + 2 = 2023b + 867 + 2 = 2023b + 869$。
因此 $x \equiv 869 \mod 2023$.

验证答案是否正确。

$869 \div 7$: $7 \times 124 = 868$，余数 $869 - 868 = 1$，故 $869 \equiv 1 \mod 7$。
$869 \div 289$: $289 \times 3 = 867$，余数 $869 - 867 = 2$，故 $869 \equiv 2 \mod 289$。
符合要求。

最终结果为 $869$。

代码

输出 $869$。

C++：

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int main()
{
    cout << 869 << endl;
    return 0;
}

Python：

1	print(869)